package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:普通二叉树找公共祖先
 * User:Mr.Du
 * Date:2023/9/16
 * Time:23:45
 */
public class LowestCommonAncestor {

    /**
     * 普通二叉树找公共祖先，自底向上解决，自底向上解决我们可以想到二叉树的后续遍历，左右中
     * p，q节点所处的位置分为以下几个
     * case1：p，q节点在root节点的左右两侧，返回root
     * case2：p，q节点都不在root节点的左右两侧，返回null
     * case3：p，q节点在root节点的一侧(左或右)，左为空，返回右，右为空，返回左
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root ==p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p ,q);
        if(left == null) return right;
        if(right == null) return left;
        else return root;
    }
}
